import java.util.Stack;

public class MyLinkedList {
    //博哥241202
    //数组实现栈 ，入栈时间复杂度：O(1)  出栈时间复杂度 O(1)
    //双向链表也可以当作栈来使用 ， LinkedLIst、 也可以实现 stack 的方法 ，

    //逆波兰表达式——后缀表达式
    //中缀表达式 前缀表达式
    //中缀表达式转后缀表达式 力扣150
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (!isOperation(s)) {
                Integer ret = Integer.valueOf(s);
                stack.push(ret);
            } else {
                int val2 = stack.pop();
                int val1 = stack.pop();
                switch (s) {
                    case "+":
                        Integer ret = val1 + val2;
                        stack.push(ret);
                        break;
                    case "-":
                        Integer ret1 = val1 - val2;
                        stack.push(ret1);
                        break;
                    case "*":
                        Integer ret2 = val1 * val2;
                        stack.push(ret2);
                        break;
                    case "/":
                        Integer ret3 = val1 / val2;
                        stack.push(ret3);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String val) {
        if (val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/") ) {
            return true;
        }
        return false;
    }
}
